Raja Iskandar Shah (Parameswara) mangkat pada tahun 1414 dan diwarisi oleh anaknya, Megat Iskandar Shah (1414–1424), Baginda kemudian digantikan dengan putera baginda, Sri Maharaja, yang kemudiannya mengambil gelaran "Sultan Muhammad Shah, Melaka" (1424–1444). Pada kemangkatannya dalam tahun 1444, beliau diganti oleh putera bongsunya daripada isteri kedua baginda, Puteri Rokan, iaitu Raja Ibrahim. Disebabkan mukhriz aka sob sebenarnya adalah oleh sepupu Puteri Rokan, orang-orang besar Melaka tidak setuju dan telah membunuh Raja Ibrahim dan dimakamkan dengan gelaran "Sultan Abu Syahid".

Kekanda Raja Ibrahim, Raja Kassim anak isteri pertama Tun Wati, menaiki takhta pada tahun 1445 dan memakai gelaran "Sultan Muzaffar Syah" (1445–1456) menaiki takhta dan mengisytiharkan Islam sebagai agama rasmi negeri. Pendakwah-pendakwah Islam dihantar oleh Sultan ke seluruh Kepulauan Melayu seperti Jawa, Borneo dan Filipina. Sebahagian besar penduduk Asia Tenggara pada ketika itu beragama Hindu.

Semasa pemerintahannya, pihak Siam membuat dua serangan ke atas Melaka. Serangan pertama pada tahun 1445 diketuai oleh Awi Chakra melalui darat tidak jauh dari Muar tetapi ditewaskan oleh Tun Perak dan Tun Hamzah (Tok Bongkok). Serangan kedua pihak Siam pada tahun 1456 diketuai oleh Awi Dichu melalui laut dan sekali lagi Tun Perak telah berjaya menewaskan mereka dengan mudah. Selepas dua kekalahan di darat dan laut ini, Siam tidak lagi mencuba untuk menyerang Empayar Melayu Melaka. Tun Perak telah dijadikan Bendahara dengan gelaran "Bendahara Paduka Raja". Beliau berkhidmat di bawah empat Sultan dan merupakan tulang belakang kepada perkembangan Melaka kepada mercu kekuasaannya di Kepulauan Melayu